/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-17
 * Time: 20:23
 */
public class Solution {
    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        //遍历用的结点
        ListNode cur = pHead;

        //链表a的头节点和尾节点
        ListNode aStart = null;
        ListNode aEnd = null;

        //链表b的头节点和尾节点
        ListNode bStart = null;
        ListNode bEnd = null;

        //将原来的链表分成两个小链表
        while (cur != null) {
            if (cur.val < x) {
                if (aStart == null) {
                    aStart = aEnd = cur;
                }else {
                    aEnd.next = cur;
                    aEnd = aEnd.next;
                }
            }else {
                if (bStart == null) {
                    bStart = bEnd = cur;
                }else {
                    bEnd.next = cur;
                    bEnd = bEnd.next;
                }
            }
            cur = cur.next;
        }

        //如果小于x的链表不存在
        if (aStart == null) {
            return bStart;
        }

        if (bEnd != null) {
            bEnd.next = null;
        }

        //如果都存在，那么进行拼接
        aEnd.next = bStart;

        return aStart;
    }
}
